// https://www.lintcode.com/problem/binary-tree-paths/

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void helper(TreeNode* root, vector<string>& res, string rec) {
        if (rec != "") rec += "->";
        rec += to_string(root->val);
        if (!root->left && !root->right) {
            res.push_back(rec);
            return;
        }
        if (root->left) helper(root->left, res, rec);
        if (root->right) helper(root->right, res, rec);  
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        string rec = "";
        helper(root, res, rec);
        return res;
    }
};



class Solution {
public:
    /**
     * @param root: the root of the binary tree
     * @return: all root-to-leaf paths
     */
    
    // 法一：dfs
    // void dfs (TreeNode * root, vector<string>& path, string tmp)
    // {
    //     tmp = tmp + "->" + to_string(root->val);
    //     if (!(root->left) && !(root->right)) // 注意不能if (!root)，不然缺一个叶子的节点也会被记
    //     {
    //         tmp = tmp.substr(2, tmp.length() - 2); 
    //         path.push_back(tmp);
    //         return;
    //     }
    //     if (root->left) dfs(root->left, path, tmp);
    //     if (root->right) dfs(root->right, path, tmp);
    // }
    // vector<string> binaryTreePaths(TreeNode * root) {
    //     vector<string> result;
    //     if (!root) return result;
    //     dfs(root, result, "");
    //     return result;
    // }
    
    
    // void dfs (TreeNode * root, vector<string>& path, vector<int> tmp) // tmp的vector不能传引用
    // {
    //     tmp.push_back(root->val);
    //     if (!(root->left) && !(root->right)) // 注意不能if (!root)，不然缺一个叶子的节点也会被记
    //     {
    //         string s = "";
    //         for (int i = 0; i < tmp.size() - 1; ++i)
    //         {
    //             s = s + to_string(tmp[i]) + "->";
    //         }
    //         s += to_string(tmp.back());
    //         path.push_back(s);
    //         return;
    //     }
    //     if (root->left) dfs(root->left, path, tmp);
    //     if (root->right) dfs(root->right, path, tmp);
    //     // tmp.pop_back(); 
    //     // 传引用就要pop。不传引用就不要。java的话，左和右进去之后出来都要pop一次（访问？）
    //     // 见https://gitee.com/xuzh1874/OJ/blob/master/.gitee/Basis/Algorithm/%E6%90%9C%E7%B4%A2/DFS/binary-tree-path-sum.cpp
    // }
    
    // vector<string> binaryTreePaths(TreeNode * root) {
    //     vector<string> result;
    //     vector<int> tmp;
    //     if (!root) return result;
    //     dfs(root, result, tmp);
    //     return result;
    // }
    
    // 法三：分治
    vector<string> binaryTreePaths(TreeNode * root) {
        vector<string> paths;
        if (!root) return paths;
        vector<string> left = binaryTreePaths(root->left);
        vector<string> right = binaryTreePaths(root->right);
        for (string path: left)
        {
            paths.push_back(to_string(root->val) + "->" + path);
        }
        for (string path: right)
        {
            paths.push_back(to_string(root->val) + "->" + path);
        }
        if (paths.empty()) //重要！叶子节点
        {
            paths.push_back(to_string(root->val));    
        }
        return paths;
    }
};